#-*- coding: utf-8 -*-
import sys
import math
import time
import random

def max_heapify(A, i):
    global HEAPSIZE
    l = 2 * i
    r = l + 1
    if l <= HEAPSIZE and A[l] > A[i]:
        largest = l
        pass
    else:
        largest = i
        pass
    if r <= HEAPSIZE and A[r] > A[largest]:
        largest = r
        pass
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)
        pass


def build_max_heap(A):
    global HEAPSIZE
    for i in range(int(math.floor(HEAPSIZE/2)), 0, 1):
        max_heapify(A,1)

def heap_sort(A):
    global HEAPSIZE
    build_max_heap(A)
    for i in range(len(A)-1, 1, -1):
        A[1], A[i] = A[i], A[1]
        HEAPSIZE = HEAPSIZE - 1
        max_heapify(A, 1)

def main():
    global HEAPSIZE
    #A = [sys.maxint, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1]

    for k in range(0, 10, 100):
        A = [ random.randint(0, 1000) for x in range(0, k)]
        A[0] = sys.maxint
        HEAPSIZE = len(A)-1
    #build_max_heap(A)
        t1 = time.time()
        heap_sort(A)
        t2 = time.time()
        A.pop(0)
        print k, t2-t1
        print A

main()
